package sort;

public class QuickSort {
	private long[] numberList;

	public long[] sort(long[] numberList) {
		// check for empty or null array
		if (numberList == null || numberList.length == 0) {
			return numberList;
		}
		this.numberList = numberList;
		quicksort(0, numberList.length - 1);
		return this.numberList;
	}

	public long calculatePivot(long[] list, int begin, int end) {
		long pivot;
		// first
		// pivot = list[0];
		
		
		// center
		// int center = ((end - 1) - begin) / 2;
		// pivot = list[center];
		
		
		// last
		// pivot = list[end];
		
		
		// median from first middle and last
		long first = list[begin];
		long middle = list[((end - 1) - begin) / 2];
		long last = list[end];

		if ((first > middle && first < last)
				|| (first < middle && first > last)) {
			pivot = first;
		} else if ((middle > first && middle < last)
				|| (middle < first && middle > last)) {
			pivot = middle;
		} else
			pivot = last;

		return pivot;
	}

	// quicksort over a section of the list
	public void quicksort(int first, int last) {
		int left = first;
		int right = last;
		// long pivot = numberList[(int) ((last - first) / 2)];
		long pivot = numberList[first + (last - first) / 2];

		while (first <= last) {
			// left to right
			// look for a number bigger than the pivot
			while (numberList[first] < pivot) {
				first++;
			}
			// right to left
			// look for a number smaller than the pivot
			while (numberList[last] > pivot) {
				last--;
			}
			// exchange
			if (first < last) {
				// exchange numbers which are positioned wrong
				exchange(first, last);
				// next position
				first++;
				last--;
			}
		}
		// if "list" is bigger than 0
		// use quicksort on it
		if (left < last)
			quicksort(left, last);
		if (right > first)
			quicksort(first, right);
	}

	private void exchange(int i, int j) {
		// exchange a number from one list to another
		long temp = numberList[i];
		numberList[i] = numberList[j];
		numberList[j] = temp;
	}
}
